W1. Algorithms, Algorithm Correctness and Analysis, Asymptotic Notation

1. Summary

1.1 What is an Algorithm?

An algorithm is a well-defined computational procedure that takes some value (or set of values) as input and produces some value (or set of values) as output in a finite amount of time. In other words, an algorithm is a sequence of computational steps that transform the input into the output.

Another way to think about it: an algorithm is a tool for solving a well-specified computational problem. The problem statement describes the desired input/output relationship in general terms, and the algorithm provides a specific procedure that achieves this relationship for all valid problem instances.

1.1.1 Computational Problems

A computational problem specifies, in general terms, the desired relationship between input and output. Here are several classic examples:

• Exponentiation Problem:
  • Input: Numbers \(a\) and \(n\).
  • Output: A number \(r\) such that \(r = a^n\).
• Prime Factorization Problem:
  • Input: A natural number \(n > 1\).
  • Output: A sequence of numbers \(\langle p_1, \dots, p_k \rangle\) such that each \(p_i\) is prime and \(\prod_{i=1}^k p_i = n\).
• Search Problem:
  • Input: A sequence of \(n\) numbers \(\langle a_1, a_2, \dots, a_n \rangle\) and a number \(x\).
  • Output: An index \(i\) such that \(a_i = x\) (if such an index exists), or a special value NOT FOUND (otherwise).
• Sorting Problem:
  • Input: A sequence of \(n\) numbers \(\langle a_1, a_2, \dots, a_n \rangle\).
  • Output: A permutation (rearrangement) \(\langle a'_1, a'_2, \dots, a'_n \rangle\) of the input such that \(a'_1 \le a'_2 \le \dots \le a'_n\).

1.2 Algorithm Correctness

An algorithm is correct if, for every valid input (as defined by the computational problem), it:

1. Terminates in finite time, and
2. Produces a correct output (as defined by the computational problem).

For example, a correct search algorithm for any finite input sequence \(\langle a_1, \dots, a_n \rangle\) and a number \(x\) must terminate in finite time and produce either an index \(i\) with \(a_i = x\), or the value NOT FOUND if no such index exists.

1.2.1 Approaches to Proving Correctness

There are three main approaches to establishing that an algorithm is correct:

1. Testing — running the implementation (or tracing pseudocode) on specific example inputs. This can reveal bugs but cannot prove correctness in general.
2. Pen-and-paper proof — a mathematical argument showing correctness for all valid inputs.
3. Formal verification — a computer-checked proof of correctness using proof assistants (e.g., Coq, Isabelle). This is the most rigorous approach but also the most labor-intensive.

1.2.2 Loop Invariants

Most algorithms rely on loops (for-loops, while-loops). To prove a loop correct, we use a loop invariant — a property (usually expressed in terms of the loop’s variables) that holds true on every iteration of the loop.

Think of a loop invariant as a promise the loop makes to itself: “No matter how many times I’ve executed, this property is still true.” This property remains true throughout the loop’s execution, even as the variables change.

To prove a loop invariant \(P\), we must show three things:

1. Initialization: \(P\) holds before the first iteration of the loop.
   • This establishes that our invariant is true when we start.
   • Like proving the base case in mathematical induction.
2. Maintenance: If \(P\) holds before an iteration, then it still holds after that iteration.
   • This shows that one execution of the loop body preserves the invariant.
   • Like proving the inductive step: if true for iteration \(i\), then true for iteration \(i+1\).
   • We must show this works for any iteration, not just specific ones.
3. Termination: The loop terminates, and when it does, \(P\) gives us a useful property that helps show the algorithm is correct.
   • We must prove the loop doesn’t run forever.
   • When the loop stops, the invariant (plus the termination condition) should give us what we need to prove correctness.

Connection to mathematical induction: Loop invariants are directly analogous to mathematical induction:

• Base case (n=0 or n=1) → Initialization (before first iteration)
• Inductive step (if true for n, then true for n+1) → Maintenance (if true before iteration, then true after)
• The difference is that loops have a termination condition, whereas induction proves the statement for all natural numbers.

1.2.3 Loop Invariant Example: Exponentiation

Consider the following algorithm that computes \(a^n\):

function exp(a, n)
begin
    k := 0
    b := 1
    while k != n do
    begin
        k := k + 1
        b := b * a
    end
    return b
end

Loop invariant: \(b = a^k\).

Proof:

1. Initialization: Before the first iteration, \(b = 1\) and \(k = 0\). Since \(a^0 = 1\) for any \(a\), the invariant holds.
2. Maintenance: Suppose before iteration \(i\) we have \(b_i = a^{k_i}\) and \(k_i \ne n\). After the iteration, \(k_{i+1} = k_i + 1\) and \(b_{i+1} = b_i \cdot a = a^{k_i} \cdot a = a^{k_i + 1} = a^{k_{i+1}}\). The invariant holds.
3. Termination: Since \(k\) starts at some value less than \(n\) and increases by 1 each iteration, the loop terminates after at most \(n\) iterations with \(k = n\). At that point, the invariant gives \(b = a^n\), which is the desired output.

1.3 Algorithm Analysis

Algorithm analysis answers the question: How do the resource requirements of an algorithm scale with the size of the input data?

The “resources” we typically measure are:

• Execution time (time complexity)
• Additional memory (space complexity)

The “input size” depends on the problem:

• Number of items in a collection
• Length of a string
• Number of digits (or bits) in a number
• Dimensions of a matrix, etc.

1.3.1 Why Analyze Algorithms?

Algorithm analysis allows us to:

1. Methodically compare different approaches to a problem.
2. Determine whether a given algorithm fits resource requirements.
3. Identify optimization opportunities.

Crucially, all of this is possible before investing time and money into a full implementation.

1.3.2 Empirical vs. Theoretical Analysis

There are two main approaches to algorithm analysis:

Empirical approach:

1. Implement the algorithm.
2. Run it on inputs of different sizes (and forms).
3. Measure the running time.
4. Plot the results and find the best approximating curve.

This approach is practical but has limitations: results depend on hardware, programming language, specific inputs chosen, and may not reveal worst-case behavior.

Theoretical (analytical) approach:

1. Describe the algorithm as pseudocode (a high-level description that abstracts away implementation details).
2. Characterize its running time as a function \(T(n)\) of the input size \(n\).

This approach gives hardware-independent results and can reveal the true asymptotic growth rate.

What is pseudocode? Pseudocode is a simplified programming language that represents the essential logic of an algorithm without worrying about syntax details. It’s designed to be readable by humans and easy to analyze mathematically. In this course, we follow the CLRS (Cormen et al.) pseudocode conventions, which include:

• Variables: Assigned with := (e.g., x := 5)
• Arrays: 1-indexed by default (e.g., A[1] is the first element)
• Loops: for i = 1 to n (inclusive), while condition
• Indentation: Shows block structure (like Python)
• Comments: Typically written as // comment or in special blocks

1.3.3 Input Size and Running Time

The running time \(T(n)\) is typically expressed as a function of a single input-size parameter \(n\), though sometimes multiple parameters are needed (e.g., \(T(n, k)\)).

An important subtlety: the running time may depend not just on the size of the input, but also on its structure. For example, incrementing a number in decimal:

• 8456103473641089382376460123862354289341286512300012 — only one digit changes.
• 8456103473641089382379999999999999999999999999999999 — 32 digits need to be updated.

Both inputs have the same size (number of digits), but the running time differs. This motivates analyzing different cases.

1.3.4 Best, Average, and Worst Case

When analyzing an algorithm, we must choose which inputs to consider:

• Best case — the input that causes the algorithm to run fastest. Often not very informative.
• Average case — the expected running time over all inputs (or a distribution of inputs). Useful in practice but harder to analyze.
• Worst case — the input that causes the algorithm to run slowest. This is the default choice because it provides a guaranteed upper bound on running time — no input can cause the algorithm to perform worse.

1.3.5 Computing Running Time

To compute the running time \(T(n)\), we estimate the contribution of each instruction by considering:

• Execution cost — how much time (in abstract units) a single execution costs.
• Frequency count — how many times the instruction executes.

We then sum up the contributions of all instructions.

1.3.6 The RAM Model

For theoretical analysis, we use the RAM (Random-Access Machine) model:

1. Instructions execute one after another (no concurrency).
2. Each basic operation (\(+, -, \times, \div, :=, \le\), etc.) takes 1 unit of time.
3. Loops and subroutine calls are not basic operations (their cost depends on how many times they execute).
4. Each memory access (read or write) takes 1 unit of time.

Under this model, we analyze worst-case time complexity.

1.3.7 Insertion Sort Analysis

Insertion Sort is a simple sorting algorithm that works like how you might sort playing cards in your hand. You start with an empty left hand and cards face down on the table. Then you remove one card at a time from the table and insert it into the correct position in your left hand. To find the correct position, you compare the new card with each card already in your hand, from right to left.

Here’s the pseudocode:

INSERTION-SORT(A, n)
1   for i = 2 to n
2       key = A[i]
3       j = i - 1
4       while j > 0 and A[j] > key
5           A[j + 1] = A[j]
6           j = j - 1
7       A[j + 1] = key

How it works:

• The algorithm maintains a sorted subarray A[1…i-1]
• In each iteration, it takes A[i] and inserts it into its correct position in the sorted part
• It does this by shifting larger elements one position to the right

Example: Sorting [5, 2, 4, 6, 1, 3]

• Start: [5 | 2, 4, 6, 1, 3] (sorted | unsorted)
• i=2: [2, 5 | 4, 6, 1, 3] (insert 2)
• i=3: [2, 4, 5 | 6, 1, 3] (insert 4)
• i=4: [2, 4, 5, 6 | 1, 3] (insert 6, no shift needed)
• i=5: [1, 2, 4, 5, 6 | 3] (insert 1, shift all)
• i=6: [1, 2, 3, 4, 5, 6 | ] (insert 3)

Time complexity analysis:

For worst-case analysis (array sorted in reverse order), we compute the cost of each line multiplied by how many times it executes:

Line	Cost	Times	Contribution
1	\(c_1\)	\(n\)	\(c_1 n\)
2	\(c_2\)	\(n-1\)	\(c_2(n-1)\)
3	\(c_3\)	\(n-1\)	\(c_3(n-1)\)
4	\(c_4\)	\(\sum_{i=2}^{n} t_i\)	\(c_4 \sum_{i=2}^{n} t_i\)
5	\(c_5\)	\(\sum_{i=2}^{n} (t_i - 1)\)	\(c_5 \sum_{i=2}^{n} (t_i - 1)\)
6	\(c_6\)	\(\sum_{i=2}^{n} (t_i - 1)\)	\(c_6 \sum_{i=2}^{n} (t_i - 1)\)
7	\(c_7\)	\(n-1\)	\(c_7(n-1)\)

where \(t_i\) is the number of times the while-loop test executes for each value of \(i\).

In the worst case (reverse sorted array), \(t_i = i\) for each \(i\). Therefore: \[\sum_{i=2}^{n} t_i = \sum_{i=2}^{n} i = \frac{n(n+1)}{2} - 1\]

Summing all contributions gives: \[T(n) = \left(\frac{c_4}{2} + \frac{c_5}{2} + \frac{c_6}{2}\right)n^2 + \left(c_1 + c_2 + c_3 + c_4 + \frac{c_5}{2} + \frac{c_6}{2} + c_7\right)n + \text{(lower order terms)}\]

This simplifies to \(an^2 + bn + c\) for some constants \(a, b, c\), which is \(\Theta(n^2)\) in the worst case.

Key insight: The inner while-loop can run up to \(i-1\) times for each value of \(i\), and summing \(\sum_{i=2}^{n}(i-1) = \frac{n(n-1)}{2} = \Theta(n^2)\) gives the quadratic term.

1.4 Asymptotic Notation

Working with exact expressions for \(T(n)\) is cumbersome and obscures the essential behavior. What matters is the order of growth — how \(T(n)\) scales as \(n\) grows large.

Why do we need this? Consider two algorithms:

• Algorithm A takes time \(T_A(n) = 1000n\)
• Algorithm B takes time \(T_B(n) = n^2\)

For small inputs (say, \(n = 10\)), Algorithm A takes 10,000 units while Algorithm B takes only 100 units. But for large inputs (say, \(n = 10,000\)), Algorithm A takes 10,000,000 units while Algorithm B takes 100,000,000 units — 10 times slower! The constant factor (1000) becomes irrelevant as \(n\) grows. What matters is whether the algorithm is linear (\(n\)) or quadratic (\(n^2\)).

Asymptotic notation provides a way to describe this growth rate by:

• Ignoring lower-order terms (e.g., \(n^2 + 5000n \to O(n^2)\))
  • For large \(n\), the \(n^2\) term dominates. When \(n = 1,000,000\), we have \(n^2 = 1,000,000,000,000\) but \(5000n = 5,000,000,000\) — the \(n^2\) term is 200,000 times larger!
• Ignoring constant factors (e.g., \(6n \to O(n)\))
  • Constants like 6 depend on implementation details (programming language, compiler optimization, hardware). We care about the fundamental shape of growth, not these details.

1.4.1 \(O\)-notation (Big-O) — Upper Bound

\(O(g(n))\) is the set of functions that grow no faster than \(g(n)\), up to a constant factor: \[O(g(n)) = \{f(n) \mid \exists\, c > 0,\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le f(n) \le c \cdot g(n)\}\]

What does this mean in plain English?

Intuitively, \(f(n) = O(g(n))\) means “\(f\) grows at most as fast as \(g\).” More precisely:

• There exists some constant \(c\) such that \(f(n) \le c \cdot g(n)\)
• This inequality doesn’t have to hold for all \(n\), just for all \(n\) beyond some threshold \(n_0\)
• For small values of \(n\) (before \(n_0\)), \(f(n)\) can be larger than \(c \cdot g(n)\) — we don’t care about small inputs
• The constants \(c\) and \(n_0\) can be any positive numbers — we just need to find some that work

Visual intuition: Imagine plotting \(f(n)\) and \(c \cdot g(n)\) on a graph. Big-O says: “After some point \(n_0\), the function \(f(n)\) stays below the scaled version \(c \cdot g(n)\).” The function \(g(n)\) (scaled by \(c\)) acts as an upper bound or ceiling for \(f(n)\).

To prove \(f(n) = O(g(n))\):

1. State the formal definition.
2. Choose specific values for \(c\) and \(n_0\).
3. Show that \(0 \le f(n) \le c \cdot g(n)\) for all \(n \ge n_0\).

Example: Prove \(4n^2 + 100n + 500 = O(n^2)\).

Divide by \(n^2\): we need \(4 + \frac{100}{n} + \frac{500}{n^2} \le c\). Setting \(n_0 = 1\): the left side is at most \(4 + 100 + 500 = 604\). So \(c = 604\) works. Alternatively, setting \(n_0 = 100\): the left side is at most \(4 + 1 + 0.05 = 5.05 < 6\), so \(c = 6\) works.

To prove \(f(n) \ne O(g(n))\):

Show that for any positive \(c\) and \(n_0\), there exists \(n \ge n_0\) such that \(f(n) > c \cdot g(n)\).

Example: Prove \(n^3 - 100n^2 \ne O(n^2)\).

We need: for any \(c, n_0 > 0\), find \(n \ge n_0\) with \(n^3 - 100n^2 > cn^2\). Dividing by \(n^2\): \(n - 100 > c\). Setting \(n = \max(c + 101, n_0)\) satisfies the inequality.

1.4.2 \(\Omega\)-notation (Big-Omega) — Lower Bound

\(\Omega(g(n))\) is the set of functions that grow at least as fast as \(g(n)\): \[\Omega(g(n)) = \{f(n) \mid \exists\, c > 0,\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le c \cdot g(n) \le f(n)\}\]

What does this mean in plain English?

Intuitively, \(f(n) = \Omega(g(n))\) means “\(f\) grows at least as fast as \(g\).” More precisely:

• There exists some constant \(c\) such that \(f(n) \ge c \cdot g(n)\)
• This inequality holds for all \(n\) beyond some threshold \(n_0\)
• The function \(g(n)\) (scaled by \(c\)) acts as a lower bound or floor for \(f(n)\)

Key difference from Big-O: Big-O is an upper bound (ceiling), while Big-Omega is a lower bound (floor). Together, they “sandwich” a function:

• \(f(n) = O(g(n))\) says: “\(f\) doesn’t grow faster than \(g\)”
• \(f(n) = \Omega(g(n))\) says: “\(f\) doesn’t grow slower than \(g\)”

Example: Prove \(4n^2 + 100n + 500 = \Omega(n^2)\).

We need \(cn^2 \le 4n^2 + 100n + 500\). Set \(c = 4, n_0 = 1\): \(4n^2 \le 4n^2 + 100n + 500\) clearly holds.

Example: Prove \(\frac{n^2}{100} - 100n - 500 = \Omega(n^2)\).

Divide by \(n^2\): \(c \le \frac{1}{100} - \frac{100}{n} - \frac{500}{n^2}\). For large enough \(n\), the right side is positive. Setting \(n_0 = 500^2 = 250000\): the right side exceeds \(\frac{1}{200}\). So \(c = \frac{1}{200}\) works.

1.4.3 \(\Theta\)-notation (Theta) — Tight Bound

\(\Theta(g(n))\) is the set of functions that grow at the same rate as \(g(n)\): \[\Theta(g(n)) = \{f(n) \mid \exists\, c_1, c_2, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le c_1 g(n) \le f(n) \le c_2 g(n)\}\]

What does this mean in plain English?

The function \(f\) is “sandwiched” between \(c_1 g(n)\) and \(c_2 g(n)\). In other words:

• \(f(n)\) grows neither faster nor slower than \(g(n)\) — they grow at the same rate
• Both the upper bound (\(c_2 g(n)\)) and lower bound (\(c_1 g(n)\)) use the same function \(g(n)\)
• This is the most precise asymptotic bound — it pins down the growth rate exactly

Visual intuition: Imagine \(f(n)\) trapped between two scaled versions of \(g(n)\). No matter how you zoom in or out on the graph, \(f(n)\) stays within this “channel” defined by \(c_1 g(n)\) and \(c_2 g(n)\).

Theorem 3.1: \(f(n) = \Theta(g(n))\) if and only if \(f(n) = O(g(n))\) and \(f(n) = \Omega(g(n))\).

Why is this useful? To prove a tight bound \(\Theta\), we can:

1. First prove the upper bound: \(f(n) = O(g(n))\)
2. Then prove the lower bound: \(f(n) = \Omega(g(n))\)
3. Conclude: \(f(n) = \Theta(g(n))\)

This is often easier than directly finding constants \(c_1\) and \(c_2\) for the \(\Theta\) definition.

1.4.4 \(o\)-notation (Little-o) — Strict Upper Bound

\(o(g(n))\) is the set of functions that grow strictly slower than \(g(n)\): \[o(g(n)) = \{f(n) \mid \forall\, c > 0,\, \exists\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le f(n) < c \cdot g(n)\}\]

What does this mean in plain English?

Little-o is like Big-O, but strict — \(f(n)\) grows strictly slower than \(g(n)\). The key differences:

• Big-O (\(O\)): The condition must hold for some constant \(c\) (we get to choose \(c\))
• Little-o (\(o\)): The condition must hold for all constants \(c\) (even arbitrarily small ones)

This is analogous to the difference between \(\le\) (less than or equal) and \(<\) (strictly less than):

• \(f(n) = O(g(n))\) is like “\(f \le g\)” (can be equal)
• \(f(n) = o(g(n))\) is like “\(f < g\)” (must be strictly less)

Limit characterization: An equivalent and often easier way to think about little-o: \[f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\]

This says: “\(f\) becomes negligible compared to \(g\) as \(n\) grows.”

Examples:

• \(n = o(n^2)\) ✓ (linear grows strictly slower than quadratic)
• \(n^2 \ne o(n^2)\) ✗ (a function doesn’t grow strictly slower than itself)
• \(100n = o(n^2)\) ✓ (constants don’t matter; linear still grows strictly slower than quadratic)

1.4.5 \(\omega\)-notation (Little-omega) — Strict Lower Bound

\(\omega(g(n))\) is the set of functions that grow strictly faster than \(g(n)\): \[\omega(g(n)) = \{f(n) \mid \forall\, c > 0,\, \exists\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le c \cdot g(n) < f(n)\}\]

What does this mean in plain English?

Little-omega is like Big-Omega, but strict — \(f(n)\) grows strictly faster than \(g(n)\).

Limit characterization: \[f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\]

This says: “\(f\) grows so much faster than \(g\) that their ratio goes to infinity.”

Relationship between little-o and little-omega: \[f(n) = o(g(n)) \iff g(n) = \omega(f(n))\]

Just like how Big-O and Big-Omega are symmetric, little-o and little-omega are also symmetric.

Summary of all five notations:

Notation	Meaning	Analogy	Limit Test
\(f = O(g)\)	\(f\) grows at most as fast as \(g\)	\(\le\)	\(\limsup \frac{f}{g} < \infty\)
\(f = \Omega(g)\)	\(f\) grows at least as fast as \(g\)	\(\ge\)	\(\liminf \frac{f}{g} > 0\)
\(f = \Theta(g)\)	\(f\) grows at the same rate as \(g\)	\(=\)	\(0 < \lim \frac{f}{g} < \infty\)
\(f = o(g)\)	\(f\) grows strictly slower than \(g\)	\(<\)	\(\lim \frac{f}{g} = 0\)
\(f = \omega(g)\)	\(f\) grows strictly faster than \(g\)	\(>\)	\(\lim \frac{f}{g} = \infty\)

1.4.6 Proper Usage of Asymptotic Notation

When stating complexity results, precision matters:

• “The worst-case running time of insertion sort is \(O(n^2)\)” — Correct (upper bound on worst case).
• “The worst-case running time of insertion sort is \(\Omega(n^2)\)” — Correct (lower bound on worst case).
• “The worst-case running time of insertion sort is \(\Theta(n^2)\)” — Correct (tight bound on worst case).
• “The running time of insertion sort is \(\Theta(n^2)\)” — Incorrect. Without specifying worst/best/average case, this is ambiguous (the best case is \(\Theta(n)\)).
• “This algorithm runs in at least \(O(n^2)\)” — Bad terminology. \(O\) denotes an upper bound; “at least” implies a lower bound. Use “at least \(\Omega(n^2)\)” instead.

1.4.7 Asymptotic Notation in Formulas

Asymptotic notation can appear inside formulas as a placeholder for an anonymous function. For example:

• \(2n^2 + 3n + 1 = 2n^2 + \Theta(n)\) means there exists a function \(f(n) = \Theta(n)\) such that \(2n^2 + 3n + 1 = 2n^2 + f(n)\).
• \(\sum_{i=1}^n O(i)\) means \(\sum_{i=1}^n f(i)\) where \(f(n) = O(n)\).

In chains of equations, each equality is interpreted independently.

1.5 Properties of Asymptotic Notation

The asymptotic notations satisfy several useful algebraic properties that make them easy to work with:

• Reflexivity: \(f(n) = \Theta(f(n))\), \(f(n) = O(f(n))\), \(f(n) = \Omega(f(n))\).
  • Every function is an upper bound, lower bound, and tight bound for itself.
  • Intuitively: \(f\) grows exactly as fast as itself!
• Transitivity: If \(f(n) = \Theta(g(n))\) and \(g(n) = \Theta(h(n))\), then \(f(n) = \Theta(h(n))\).
  • This holds for all five notations (\(O, \Omega, \Theta, o, \omega\)).
  • This lets us “chain” relationships: if \(f\) grows like \(g\) and \(g\) grows like \(h\), then \(f\) grows like \(h\).
• Symmetry: \(f(n) = \Theta(g(n))\) if and only if \(g(n) = \Theta(f(n))\).
  • Theta (\(\Theta\)) is symmetric — it’s a true “equivalence” relation.
  • If \(f\) and \(g\) grow at the same rate, then saying “\(f = \Theta(g)\)” or “\(g = \Theta(f)\)” is equivalent.
• Transpose symmetry: \(f(n) = O(g(n))\) if and only if \(g(n) = \Omega(f(n))\).
  • Similarly, \(f(n) = o(g(n))\) if and only if \(g(n) = \omega(f(n))\).
  • Upper bounds and lower bounds are “dual” to each other.
  • If \(f\) is bounded above by \(g\), then \(g\) is bounded below by \(f\).
• No trichotomy: Unlike real numbers (where exactly one of \(a < b\), \(a = b\), \(a > b\) holds), for functions it is possible that none of \(f = o(g)\), \(f = \Theta(g)\), \(f = \omega(g)\) hold.
  • Why? Some functions oscillate or behave erratically.
  • Example: Let \(f(n) = n^{1 + \sin n}\). This function oscillates between growing like \(n^0 = 1\) (when \(\sin n = -1\)) and growing like \(n^2\) (when \(\sin n = 1\)). It doesn’t have a consistent relationship with, say, \(g(n) = n\).
  • Practical note: Most functions we encounter in algorithm analysis (polynomials, logarithms, exponentials) do satisfy trichotomy.

1.6 Common Functions and Asymptotic Growth

Understanding how common function families compare asymptotically is essential for algorithm analysis. This section provides a “hierarchy” of growth rates you’ll encounter frequently.

1.6.1 Polynomials

A polynomial of degree \(d\): \(p(n) = a_d n^d + a_{d-1} n^{d-1} + \dots + a_1 n + a_0\) (with \(a_d > 0\)) satisfies: \[p(n) = \Theta(n^d)\]

Key insight: Only the highest-degree term matters! A polynomial of degree \(d\) always grows like \(n^d\), regardless of the lower-degree terms or constant coefficients.

Examples:

• \(3n^2 + 100n + 5 = \Theta(n^2)\)
• \(n^3 - 1000n^2 = \Theta(n^3)\)
• \(7n = \Theta(n)\)

Comparison: Higher-degree polynomials always grow faster: \[n \prec n^2 \prec n^3 \prec n^4 \prec \dots\] where \(\prec\) means “grows strictly slower than.”

1.6.2 Exponentials

Exponential functions grow faster than any polynomial, no matter how large the polynomial degree: \[n^b = o(a^n) \quad \text{for any constant } a > 1 \text{ and any constant } b\]

Why is this important? Algorithms with exponential running time (like \(2^n\) or \(3^n\)) become impractical very quickly, even for moderate input sizes. For example:

• \(n = 30\): \(n^{10} \approx 5.9 \times 10^{14}\), but \(2^n \approx 1.1 \times 10^9\) (polynomial is actually larger here)
• \(n = 100\): \(n^{10} \approx 10^{20}\), but \(2^n \approx 1.3 \times 10^{30}\) (exponential dominates)
• \(n = 1000\): \(n^{10} \approx 10^{30}\), but \(2^n \approx 10^{301}\) (exponential is astronomically larger)

Practical note: Even \(2^{100}\) is computationally infeasible (more than the number of atoms in the universe!).

1.6.3 Logarithms

Polylogarithmic functions (powers of logarithms) grow slower than any polynomial with a positive exponent: \[\log^b n = o(n^a) \quad \text{for any constants } a > 0 \text{ and } b\]

What is \(\log^b n\)? This means \((\log n)^b\), not \(\log(\log(\dots\log n))\).

Examples:

• \(\log n = o(n)\) (logarithm grows slower than linear)
• \((\log n)^2 = o(n^{0.1})\) (even squared logarithm grows slower than any polynomial)
• \(n \log n = o(n^{1.01})\) (algorithm with \(n \log n\) time is nearly linear)

Why logarithms appear: Many efficient algorithms (like binary search, merge sort, heap operations) have logarithmic or \(n \log n\) running times because they repeatedly divide the problem size.

Logarithm base doesn’t matter: \(\log_a n = \frac{\log_b n}{\log_b a}\), and \(\frac{1}{\log_b a}\) is just a constant. So: \[\log_2 n = \Theta(\log_{10} n) = \Theta(\ln n)\] For asymptotic analysis, we usually just write \(\log n\) without specifying the base.

1.6.4 Factorials

The factorial function \(n! = n \times (n-1) \times \cdots \times 2 \times 1\) appears in algorithms that generate permutations or subsets.

Key facts about \(n!\):

• Upper bound: \(n! \le n^n\) (multiply \(n\) copies of \(n\))
• Lower bound: \(n! \ge (n/2)^{n/2}\) (at least half the factors are \(\ge n/2\))
• Stirling’s approximation: \(n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1 + \Theta\left(\frac{1}{n}\right)\right)\)
  • This gives an extremely accurate estimate for large \(n\)
  • Useful for: \(\log(n!) = \Theta(n \log n)\)

Growth comparisons:

• \(n! = o(n^n)\) — factorials grow slower than \(n^n\)
• \(n! = \omega(2^n)\) — factorials grow faster than \(2^n\)
• In fact: \(n! = \Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)\) (from Stirling)

The complete hierarchy (from slowest to fastest growth): \[1 \prec \log \log n \prec \log n \prec (\log n)^2 \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n \prec n! \prec n^n\]

Practical interpretation:

• Constant (\(1\)): Best possible — no dependence on input size
• Logarithmic (\(\log n\)): Excellent — typically from divide-and-conquer
• Linear (\(n\)): Good — must at least look at every input element
• Linearithmic (\(n \log n\)): Good — optimal for comparison-based sorting
• Quadratic (\(n^2\)): Acceptable for small inputs, Taskatic for large
• Cubic (\(n^3\)) and higher: Problematic unless \(n\) is small
• Exponential (\(2^n\), \(n!\), \(n^n\)): Intractable for even moderate \(n\) (typically \(n > 30\))

---

2. Definitions

• Algorithm: A well-defined computational procedure that takes input and produces output in a finite amount of time. It is a sequence of computational steps that transform the input into the output.
• Computational problem: A specification of the desired input/output relationship, defining what constitutes valid inputs and correct outputs for all problem instances.
• Correct algorithm: An algorithm that, for every valid input, terminates in finite time and produces a correct output as defined by the computational problem.
• Loop invariant: A property (expressed in terms of the loop’s variables) that holds true before and after every iteration of a loop, used to prove the correctness of loop-based algorithms through initialization, maintenance, and termination.
• Algorithm analysis: The study of how an algorithm’s resource requirements (time, memory) scale with input size, typically focusing on worst-case behavior.
• Time complexity: A measure of how the running time of an algorithm grows as a function of input size, usually expressed in asymptotic notation.
• Space complexity: A measure of how much additional memory an algorithm requires as a function of input size.
• Input size: A measure of the amount of data fed to an algorithm (e.g., number of elements, string length, number of bits, matrix dimensions).
• Running time \(T(n)\): The total number of primitive operations executed by an algorithm as a function of input size \(n\).
• Best-case analysis: Analyzing an algorithm’s performance on the input that causes it to run the fastest.
• Average-case analysis: Analyzing an algorithm’s expected performance over all possible inputs (or a distribution of inputs).
• Worst-case analysis: Analyzing an algorithm’s performance on the input that causes it to run the slowest, providing a guaranteed upper bound on running time.
• RAM model (Random-Access Machine): A theoretical computation model where each basic operation (\(+, -, \times, \div, :=\), comparisons) and memory access takes 1 unit of time, and instructions execute sequentially.
• Execution cost: The time (in abstract units) required to execute a single instance of an instruction in the RAM model.
• Frequency count: The number of times a particular instruction is executed during the algorithm’s run for a given input.
• Asymptotic notation: Mathematical notation (\(O, \Omega, \Theta, o, \omega\)) for describing the growth rate of functions as input size approaches infinity, ignoring constant factors and lower-order terms.
• Order of growth: The rate at which a function increases as its input grows, typically characterized using the dominant term (highest-order term).
• \(O\)-notation (Big-O): Denotes an asymptotic upper bound; \(f(n) = O(g(n))\) means there exist constants \(c > 0\) and \(n_0 > 0\) such that \(f(n) \le c \cdot g(n)\) for all \(n \ge n_0\).
• \(\Omega\)-notation (Big-Omega): Denotes an asymptotic lower bound; \(f(n) = \Omega(g(n))\) means there exist constants \(c > 0\) and \(n_0 > 0\) such that \(f(n) \ge c \cdot g(n)\) for all \(n \ge n_0\).
• \(\Theta\)-notation (Theta): Denotes a tight asymptotic bound; \(f(n) = \Theta(g(n))\) means \(f(n) = O(g(n))\) and \(f(n) = \Omega(g(n))\), i.e., \(f\) and \(g\) grow at the same rate.
• \(o\)-notation (Little-o): Denotes a strict upper bound; \(f(n) = o(g(n))\) means for all \(c > 0\), there exists \(n_0\) such that \(f(n) < c \cdot g(n)\) for all \(n \ge n_0\). Equivalently, \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\).
• \(\omega\)-notation (Little-omega): Denotes a strict lower bound; \(f(n) = \omega(g(n))\) means for all \(c > 0\), there exists \(n_0\) such that \(f(n) > c \cdot g(n)\) for all \(n \ge n_0\). Equivalently, \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\).
• Pseudocode: A high-level, semi-formal description of an algorithm that abstracts away implementation details to facilitate mathematical analysis and improve readability.

---

3. Formulas

• \(O\)-notation: \(O(g(n)) = \{f(n) \mid \exists\, c, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le f(n) \le c \cdot g(n)\}\)
• \(\Omega\)-notation: \(\Omega(g(n)) = \{f(n) \mid \exists\, c, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le c \cdot g(n) \le f(n)\}\)
• \(\Theta\)-notation: \(\Theta(g(n)) = \{f(n) \mid \exists\, c_1, c_2, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le c_1 g(n) \le f(n) \le c_2 g(n)\}\)
• \(o\)-notation: \(o(g(n)) = \{f(n) \mid \forall\, c > 0.\ \exists\, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le f(n) < c \cdot g(n)\}\)
• \(\omega\)-notation: \(\omega(g(n)) = \{f(n) \mid \forall\, c > 0.\ \exists\, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le c \cdot g(n) < f(n)\}\)
• Theorem 3.1 (\(\Theta\) decomposition): \(f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))\)
• Transpose symmetry: \(f(n) = O(g(n)) \iff g(n) = \Omega(f(n))\); \(f(n) = o(g(n)) \iff g(n) = \omega(f(n))\)
• Polynomial growth: For \(p(n) = a_d n^d + \dots + a_0\) with \(a_d > 0\): \(p(n) = \Theta(n^d)\)
• Exponential dominates polynomial: \(n^b = o(a^n)\) for \(a > 1\)
• Polynomial dominates polylogarithm: \(\log^b n = o(n^a)\) for \(a > 0\)
• Stirling’s approximation: \(n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1 + \Theta\left(\frac{1}{n}\right)\right)\)
• Factorial bounds: \(n! = o(n^n)\), \(n! = \omega(2^n)\), \(\log(n!) = \Theta(n \log n)\)
• Little-o via limit: \(f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\)
• Little-omega via limit: \(f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\)

---

4. Examples

4.1. Prove Correctness and Analyze exp1 Algorithm (Lab 1, Task 1)

Prove that the following exponentiation algorithm is correct and analyze its time complexity:

function exp1(a, n)
begin
  k := n
  b := 1
  while k != 0 do
  begin
    k := k - 1
    b := b * a
  end
  return b
end

Click to see the solution

Key Concept: Use a loop invariant to prove correctness, then count loop iterations.

1. Loop Invariant: \(b \cdot a^k = a^n\) before and after each iteration.

   Initialization: Before first iteration, \(k = n\) and \(b = 1\), so \(b \cdot a^k = 1 \cdot a^n = a^n\). ✓

   Maintenance: Assume \(b \cdot a^k = a^n\) before iteration \(i\). After executing the loop body: \(k' = k - 1\) and \(b' = b \cdot a\). Then \(b' \cdot a^{k'} = (b \cdot a) \cdot a^{k-1} = b \cdot a^k = a^n\). ✓

   Termination: The loop terminates when \(k = 0\). At that point, \(b \cdot a^0 = a^n\), so \(b = a^n\). ✓

2. Time Complexity: The loop executes \(n\) times (decrementing \(k\) from \(n\) to \(0\)). Each iteration performs a multiplication and a decrement, both \(O(1)\) operations (assuming \(a\) and \(b\) fit in \(O(1)\) space). Thus, \(T(n) = \Theta(n)\).

Answer: Correctness proved via loop invariant. Time complexity: \(\Theta(n)\).

4.2. Prove Correctness and Analyze exp2 Algorithm (Lab 1, Task 2)

Prove that the following exponentiation algorithm (fast exponentiation) is correct and analyze its time complexity:

function exp2(a, n)
begin
  k := n
  b := 1
  c := a
  while k != 0 do
    if k mod 2 = 0 then
      k := k / 2
      c := c * c
    else
      k := k - 1
      b := b * c
  return b
end

Click to see the solution

Key Concept: This is binary exponentiation. The invariant is that \(b \cdot c^k = a^n\) always holds.

1. Loop Invariant: \(b \cdot c^k = a^n\) before and after each iteration.

   Initialization: \(b = 1\), \(c = a\), \(k = n\). So \(b \cdot c^k = 1 \cdot a^n = a^n\). ✓

   Maintenance: Assume \(b \cdot c^k = a^n\).

   • If \(k\) is even: \(k' = k/2\), \(c' = c^2\). Then \(b' \cdot c'^{k'} = b \cdot (c^2)^{k/2} = b \cdot c^k = a^n\). ✓
   • If \(k\) is odd: \(k' = k - 1\), \(b' = b \cdot c\). Then \(b' \cdot c'^{k'} = (b \cdot c) \cdot c^{k-1} = b \cdot c^k = a^n\). ✓

   Termination: When \(k = 0\), \(b \cdot c^0 = a^n\), so \(b = a^n\). ✓

2. Time Complexity: The variable \(k\) is either halved or decremented (if odd, we decrement once then halve on the next iteration). On average, \(k\) halves roughly every iteration. Thus, \(T(n) = \Theta(\log n)\).

Answer: Correctness proved via loop invariant. Time complexity: \(\Theta(\log n)\) — exponentially faster than exp1!

4.3. GCD Algorithm (Naive) (Lab 1, Task 3)

Prove that the following GCD algorithm is correct and analyze its time complexity:

function gcd1(a, b)
begin
  if a > b then
    k := a
  else
    k := b
  while (a mod k != 0) or (b mod k != 0) do
    k := k - 1
  return k
end

Click to see the solution

Key Concept: Find the largest \(k\) that divides both \(a\) and \(b\) by trial division from the larger value downward.

1. Correctness: By definition, \(\gcd(a, b)\) is the largest positive integer that divides both \(a\) and \(b\). The algorithm starts with \(k = \max(a, b)\) and decrements \(k\) until both \(a \mod k = 0\) and \(b \mod k = 0\). The first \(k\) satisfying this condition is the GCD.
2. Time Complexity: In the worst case, the algorithm decrements \(k\) from \(\max(a, b)\) all the way down to \(\gcd(a, b)\). For example, if \(\gcd(a, b) = 1\), it decrements from \(\max(a, b)\) to \(1\). This takes \(\Theta(\max(a, b))\) iterations. Since each iteration performs a modulo operation, the overall complexity is \(\Theta(m)\) where \(m = \max(a, b)\).

Answer: Correctness by definition of GCD. Time complexity: \(\Theta(\max(a, b))\) — very slow!

4.4. Euclidean GCD Algorithm (Lab 1, Task 4)

Prove that Euclid’s GCD algorithm is correct and analyze its time complexity:

function gcd2(a, b)
begin
  m := a
  n := b
  while (m != 0) and (n != 0) do
    if m >= n then
      m := m - n
    else
      n := n - m
  return (n + m)
end

Click to see the solution

Key Concept: The Euclidean algorithm repeatedly replaces the larger of two numbers with their difference until one becomes zero.

1. Correctness: Loop Invariant: \(\gcd(m, n) = \gcd(a, b)\) before and after each iteration.

   Initialization: \(m = a\), \(n = b\), so \(\gcd(m, n) = \gcd(a, b)\). ✓

   Maintenance: Assume \(\gcd(m, n) = \gcd(a, b)\).

   • If \(m \ge n\): Replace \(m\) with \(m - n\). By the property \(\gcd(x, y) = \gcd(x - y, y)\), we have \(\gcd(m - n, n) = \gcd(m, n)\). ✓
   • If \(m < n\): Replace \(n\) with \(n - m\). Similarly, \(\gcd(m, n - m) = \gcd(m, n)\). ✓

   Termination: The loop terminates when one variable is zero. If \(m = 0\), then \(\gcd(0, n) = n\). If \(n = 0\), then \(\gcd(m, 0) = m\). Thus, \(\gcd(a, b) = n + m\) (since exactly one is nonzero). ✓

2. Time Complexity: This algorithm is similar to the binary subtraction version of GCD. The number of iterations is \(O(\log(\min(a, b)))\) if we use division instead of repeated subtraction. With repeated subtraction as shown, it’s \(O(\max(a, b) / \min(a, b))\) in the worst case, but typically much faster than gcd1.

Answer: Correctness proved via loop invariant. Time complexity: \(O(\log(\min(a, b)))\) with division (Euclidean algorithm).

4.5. Compute Asymptotic Worst-Case Time Complexity (Problem Set 1, Task 1)

Compute asymptotic worst-case time complexity of the following algorithm (see pseudocode conventions in [CLRS, §2.1]). Use \(\Theta\)-notation. Provide full justification, including execution cost and frequency count for each line, and the details for computing \(T(n)\) for the worst case.

/* A is a 1-indexed array,
 * n is the number of items in A */
function secret(A, n)
    r := n
    while (2 * r > n)
        k := n - r + 1
        i := r
        for j = k to r
            if (A[j] < A[i])
                i := j
            if (A[j] > A[k])
                k := j
        exchange A[i] with A[r]
        exchange A[k] with A[n - r + 1]
        r := r - 1

Click to see the solution

Key Concept: We analyze each line’s cost and frequency, then sum to get \(T(n)\).

1. Determine how many times the while-loop executes.

The variable \(r\) starts at \(n\) and decreases by 1 each iteration. The loop runs while \(2r > n\), i.e., \(r > n/2\). So \(r\) goes from \(n\) down to \(\lceil n/2 \rceil + 1\) (approximately), giving roughly \(\lfloor n/2 \rfloor\) iterations of the outer loop.

2. Determine how many times the for-loop executes per outer iteration.

In each outer iteration, \(k = n - r + 1\) and the for-loop runs from \(j = k\) to \(j = r\). The number of iterations is \(r - k + 1 = r - (n - r + 1) + 1 = 2r - n\).

When \(r = n\): the for-loop runs \(2n - n = n\) times. When \(r = \lceil n/2 \rceil + 1\): the for-loop runs about \(2\) times.

3. Fill in the cost/frequency table.

Line	Code	Cost	Frequency (worst case)
4	r := n	\(c_4\)	\(1\)
5	while (2 * r > n)	\(c_5\)	\(\lfloor n/2 \rfloor + 1\)
6	k := n - r + 1	\(c_6\)	\(\lfloor n/2 \rfloor\)
7	i := r	\(c_7\)	\(\lfloor n/2 \rfloor\)
8	for j = k to r	\(c_8\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n + 1)\)
9	if (A[j] < A[i])	\(c_9\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\)
10	i := j	\(c_{10}\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\) (worst case)
11	if (A[j] > A[k])	\(c_{11}\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\)
12	k := j	\(c_{12}\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\) (worst case)
13	exchange A[i] with A[r]	\(c_{13}\)	\(\lfloor n/2 \rfloor\)
14	exchange A[k] with A[n-r+1]	\(c_{14}\)	\(\lfloor n/2 \rfloor\)
15	r := r - 1	\(c_{15}\)	\(\lfloor n/2 \rfloor\)

4. Compute the inner sum.

\[\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n) = \sum_{m=1}^{\lfloor n/2 \rfloor} 2m \quad \text{(substituting } m = r - \lceil n/2 \rceil\text{)}\]

Adjusting properly: let \(r\) range from \(\lceil n/2 \rceil + 1\) to \(n\). Then \(2r - n\) ranges from \(2\) to \(n\) (in steps of \(2\) if \(n\) is even). The sum is: \[\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n) = 2 + 4 + \dots + n \approx \frac{n^2/4 + n/2}{1} = \Theta(n^2/4) = \Theta(n^2)\]

More precisely, this sum equals \(\frac{\lfloor n/2 \rfloor(\lfloor n/2 \rfloor + 1)}{1}\) which is \(\Theta(n^2)\).

5. Compute \(T(n)\).

\[T(n) = \Theta(1) + \Theta(n) + \Theta(n^2) = \Theta(n^2)\]

Answer: \(T(n) = \Theta(n^2)\)

4.6. Loop Invariant Proof for Reorder Algorithm (Problem Set 1, Task 2)

The following algorithm manipulates elements in the input array. For example:

Input: [2, 1, 4, 3, 5, 8, 9] \(\Longrightarrow\) Output: [2, 4, 5, 8, 9, 3, 1]

/* A is a 1-indexed array,
 * n is the number of items in A */
function reorder(A, n)
    k := 0
    for i = 1 to (n - 1)
        if A[i - k] < A[i + 1]
            exchange A[i - k + 1] with A[i + 1]
        else:
            k := k + 1

Let \(n > 0\). Is it true that the element at index \((n - k)\) in the output array is always the largest element of the input array? If yes — prove it using a loop invariant. If not — provide a counterexample.

Click to see the solution

Key Concept: We need to analyze what the algorithm does and determine whether the claim holds for all inputs.

1. Trace through the example.

Input: \(A = [2, 1, 4, 3, 5, 8, 9]\), \(n = 7\).

• \(i=1, k=0\): \(A[1]=2 < A[2]=1\)? No. \(k=1\).
• \(i=2, k=1\): \(A[1]=2 < A[3]=4\)? Yes. Exchange \(A[2]\) and \(A[3]\): \([2, 4, 1, 3, 5, 8, 9]\).
• \(i=3, k=1\): \(A[2]=4 < A[4]=3\)? No. \(k=2\).
• \(i=4, k=2\): Compare \(A[4-2]=A[2]=4\) with \(A[5]=5\). \(4 < 5\)? Yes. Exchange \(A[4-2+1]=A[3]=1\) with \(A[5]=5\). Array: \([2, 4, 5, 3, 1, 8, 9]\).
• \(i=5\): Compare \(A[5-2]=A[3]=5\) with \(A[6]=8\). \(5 < 8\)? Yes. Exchange \(A[5-2+1]=A[4]=3\) with \(A[6]=8\). Array: \([2, 4, 5, 8, 1, 3, 9]\).
• \(i=6\): Compare \(A[6-2]=A[4]=8\) with \(A[7]=9\). \(8 < 9\)? Yes. Exchange \(A[6-2+1]=A[5]=1\) with \(A[7]=9\). Array: \([2, 4, 5, 8, 9, 3, 1]\).

Output: \([2, 4, 5, 8, 9, 3, 1]\), \(k = 2\). Index \(n - k = 7 - 2 = 5\). \(A[5] = 9\), which is indeed the largest element.

2. Test a counterexample.

Consider \(A = [3, 1, 2]\), \(n = 3\), \(k = 0\).

• \(i=1\): Compare \(A[1]=3\) with \(A[2]=1\). \(3 < 1\)? No. \(k = 1\).
• \(i=2\): Compare \(A[2-1]=A[1]=3\) with \(A[3]=2\). \(3 < 2\)? No. \(k = 2\).

Output: \([3, 1, 2]\), \(k = 2\). Index \(n - k = 3 - 2 = 1\). \(A[1] = 3\), which is the largest. Still works.

Consider \(A = [5, 3, 1, 2, 4]\), \(n = 5\), \(k = 0\).

• \(i=1\): \(A[1]=5, A[2]=3\). \(5<3\)? No. \(k=1\).
• \(i=2\): \(A[1]=5, A[3]=1\). \(5<1\)? No. \(k=2\).
• \(i=3\): \(A[1]=5, A[4]=2\). \(5<2\)? No. \(k=3\).
• \(i=4\): \(A[1]=5, A[5]=4\). \(5<4\)? No. \(k=4\).

Output: \([5, 3, 1, 2, 4]\), \(k=4\). Index \(n-k=1\). \(A[1]=5\). Correct again.

Consider \(A = [1, 3, 2]\), \(n = 3\), \(k = 0\).

• \(i=1\): \(A[1]=1, A[2]=3\). \(1<3\)? Yes. Exchange \(A[2]=3\) with \(A[2]=3\). Wait: \(A[i-k+1] = A[1-0+1] = A[2] = 3\) with \(A[i+1] = A[2] = 3\). Array unchanged: \([1, 3, 2]\).
• \(i=2\): \(A[2-0]=A[2]=3, A[3]=2\). \(3<2\)? No. \(k=1\).

Output: \([1, 3, 2]\), \(k=1\). Index \(n-k=2\). \(A[2]=3\). Correct.

Consider \(A = [2, 3, 1]\), \(n = 3\), \(k = 0\).

• \(i=1\): \(A[1]=2, A[2]=3\). \(2<3\)? Yes. Exchange \(A[2]\) with \(A[2]\): no change. Array: \([2, 3, 1]\).
• \(i=2\): \(A[2]=3, A[3]=1\). \(3<1\)? No. \(k=1\).

Output: \([2, 3, 1]\), \(k=1\). Index \(n-k=2\). \(A[2]=3\). Correct.

The claim appears to hold. Let us prove it using a loop invariant.

3. Loop invariant proof.

Loop invariant: After iteration \(i\), the element \(A[i - k + 1]\) is the maximum of \(\{A[1], A[2], \dots, A[i+1]\}\) (considering the original values), and it is located at index \(i - k + 1\).

More precisely: at the end of each iteration, \(A[i+1-k]\) equals the maximum element among the first \(i+1\) elements of the original array.

Initialization (\(i = 0\), before the loop): \(k = 0\). We consider the subarray of the first 1 element: \(\{A[1]\}\). The max is \(A[1]\), located at index \(1 = 1 - 0 + 0\). The invariant holds.

Maintenance: Assume after iteration \(i-1\), the max of \(\{A[1], \dots, A[i]\}\) is at index \(i - k\). In iteration \(i\):

• We compare \(A[i - k]\) (the current max) with \(A[i + 1]\) (the next element).
• Case 1: \(A[i-k] < A[i+1]\): The new max is \(A[i+1]\). We swap \(A[i-k+1]\) with \(A[i+1]\), effectively moving the new maximum to position \(i-k+1 = (i+1) - k\). The invariant holds (max is now at index \((i+1) - k\)).
• Case 2: \(A[i-k] \ge A[i+1]\): The max remains \(A[i-k]\). We increment \(k\), so the max is now at index \(i - k = i - (k+1) + 1 = (i+1) - (k+1)\). The invariant holds.

Termination: The loop terminates when \(i = n\). The invariant gives us that the max of \(\{A[1], \dots, A[n]\}\) — i.e., the largest element — is at index \(n - k\).

Answer: Yes, the statement is true. The element at index \((n - k)\) in the output array is always the largest element of the input array.

4.7. Asymptotic Notation: True or False (Problem Set 1, Task 3)

For each of the following statements determine whether it is TRUE or FALSE. Provide full justification using formal definitions and/or known properties of asymptotic notation.

1. Is it true that \(n^4 - 20n^2 - 1 = \Theta(n^4)\)?
2. Is it true that \(\log_2(\log_3 n) = O(\log_6 n)\)?
3. Is it true that \(\min(\log n, \sqrt{n}) = \Omega(\log n + \sqrt{n})\)?
4. Is it true that \(n 2^n = o(3^n)\)?
5. Is it true that \((n - 1)! = \Theta(n!)\)?

Click to see the solution

(1) Is \(n^4 - 20n^2 - 1 = \Theta(n^4)\)?

TRUE.

By the polynomial rule, any polynomial of degree \(d\) with positive leading coefficient is \(\Theta(n^d)\). Here \(f(n) = n^4 - 20n^2 - 1\) is a degree-4 polynomial with leading coefficient 1.

Formally:

• \(O\) bound: \(n^4 - 20n^2 - 1 \le n^4\). Set \(c_2 = 1, n_0 = 1\).
• \(\Omega\) bound: \(n^4 - 20n^2 - 1 \ge n^4 - 20n^2 \ge n^4 - 20n^4/n^2\). For \(n \ge 7\): \(20n^2 + 1 \le 20n^2 + n^2 = 21n^2 \le 21 \cdot \frac{n^4}{49} < \frac{n^4}{2}\). So \(f(n) \ge \frac{n^4}{2}\). Set \(c_1 = 1/2, n_0 = 7\).

By Theorem 3.1, \(f(n) = \Theta(n^4)\).

(2) Is \(\log_2(\log_3 n) = O(\log_6 n)\)?

TRUE.

Note that \(\log_3 n = \frac{\ln n}{\ln 3}\) and \(\log_6 n = \frac{\ln n}{\ln 6}\). So \(\log_6 n = \frac{\log_3 n}{\log_3 6}\).

We have \(\log_2(\log_3 n) = \frac{\ln(\log_3 n)}{\ln 2}\).

For large \(n\), \(\log_3 n\) grows without bound, so \(\log_2(\log_3 n)\) grows very slowly (it is the logarithm of a logarithm).

Meanwhile, \(\log_6 n = \Theta(\log n)\), which grows much faster than \(\log \log n\).

Since \(\log_2(\log_3 n) = \Theta(\log \log n)\) and \(\log_6 n = \Theta(\log n)\), and \(\log \log n = o(\log n)\), we have \(\log_2(\log_3 n) = O(\log_6 n)\).

(3) Is \(\min(\log n, \sqrt{n}) = \Omega(\log n + \sqrt{n})\)?

FALSE.

For large \(n\), \(\log n < \sqrt{n}\) (since \(\log n = o(\sqrt{n})\)). Therefore, \(\min(\log n, \sqrt{n}) = \log n\) for large \(n\).

Also, \(\log n + \sqrt{n} \ge \sqrt{n}\) for all \(n\).

If \(\min(\log n, \sqrt{n}) = \Omega(\log n + \sqrt{n})\), then there exist \(c, n_0\) with \(\log n \ge c(\log n + \sqrt{n}) \ge c\sqrt{n}\) for all \(n \ge n_0\).

But \(\log n = o(\sqrt{n})\), meaning \(\frac{\log n}{\sqrt{n}} \to 0\), so no such \(c > 0\) exists. Contradiction.

(4) Is \(n 2^n = o(3^n)\)?

TRUE.

We compute the limit: \[\lim_{n \to \infty} \frac{n \cdot 2^n}{3^n} = \lim_{n \to \infty} n \cdot \left(\frac{2}{3}\right)^n\]

Since \(\frac{2}{3} < 1\), the term \(\left(\frac{2}{3}\right)^n\) decreases exponentially to 0. The factor \(n\) grows only polynomially. Therefore: \[\lim_{n \to \infty} n \cdot \left(\frac{2}{3}\right)^n = 0\]

By the limit characterization of \(o\)-notation, \(n 2^n = o(3^n)\).

(5) Is \((n-1)! = \Theta(n!)\)?

FALSE.

We have \(n! = n \cdot (n-1)!\), so \(\frac{(n-1)!}{n!} = \frac{1}{n} \to 0\) as \(n \to \infty\).

This means \((n-1)! = o(n!)\), which implies \((n-1)! \ne \Theta(n!)\).

More precisely: if \((n-1)! = \Omega(n!)\), there would exist \(c > 0\) with \((n-1)! \ge c \cdot n!\) for large \(n\), i.e., \(\frac{1}{n} \ge c\), which fails for \(n > 1/c\).

Answer: (1) TRUE, (2) TRUE, (3) FALSE, (4) TRUE, (5) FALSE.

4.8. Checking the exp Algorithm on Examples (Lecture 1, Example 1)

What does the exp(a, n) algorithm compute on the following inputs?

1. \(a = 2, n = 3\)
2. \(a = 3, n = 2\)

function exp(a, n)
begin
    k := 0
    b := 1
    while k != n do
    begin
        k := k + 1
        b := b * a
    end
    return b
end

Click to see the solution

Key Concept: Trace through the algorithm step by step.

(a) \(a = 2, n = 3\):

Iteration	\(k\) (before)	\(b\) (before)	\(k\) (after)	\(b\) (after)
1	0	1	1	\(1 \times 2 = 2\)
2	1	2	2	\(2 \times 2 = 4\)
3	2	4	3	\(4 \times 2 = 8\)

Now \(k = 3 = n\), so the loop ends. Return \(b = 8 = 2^3\).

(b) \(a = 3, n = 2\):

Iteration	\(k\) (before)	\(b\) (before)	\(k\) (after)	\(b\) (after)
1	0	1	1	\(1 \times 3 = 3\)
2	1	3	2	\(3 \times 3 = 9\)

Now \(k = 2 = n\), so the loop ends. Return \(b = 9 = 3^2\).

Answer: (a) \(8\), (b) \(9\).

4.9. Prove \(2^{n+1} = O(2^n)\) (Lecture 1, Task 1)

Is \(2^{n+1} = O(2^n)\)? If yes, prove it.

Click to see the solution

Key Concept: Simplify \(2^{n+1}\) using exponent rules.

Yes, it is true.

\(2^{n+1} = 2 \cdot 2^n\).

We need \(c, n_0 > 0\) such that \(0 \le 2 \cdot 2^n \le c \cdot 2^n\) for all \(n \ge n_0\).

Set \(c = 2\) and \(n_0 = 1\). Then \(2 \cdot 2^n \le 2 \cdot 2^n\), which holds trivially.

Answer: Yes. \(2^{n+1} = O(2^n)\) with \(c = 2, n_0 = 1\).

4.10. Prove \(2^{2n} \ne O(2^n)\) (Lecture 1, Task 2)

Is \(2^{2n} = O(2^n)\)? If yes, prove it. If no, disprove it.

Click to see the solution

Key Concept: Simplify \(2^{2n}\) and show it grows too fast.

No, it is not true.

\(2^{2n} = (2^n)^2 = 4^n\).

Suppose for contradiction that \(2^{2n} = O(2^n)\). Then there exist \(c, n_0 > 0\) with \(4^n \le c \cdot 2^n\) for all \(n \ge n_0\).

Dividing by \(2^n\): \(2^n \le c\) for all \(n \ge n_0\). But \(2^n \to \infty\), so no such \(c\) exists. Contradiction.

Answer: No. \(2^{2n} \ne O(2^n)\).

4.11. Prove \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\) (Lecture 1, Task 3)

Prove that \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\), assuming \(f(n) \ge 0\) and \(g(n) \ge 0\) for all \(n\).

Click to see the solution

Key Concept: Show both \(O\) and \(\Omega\) bounds using Theorem 3.1.

\(O\) bound: Since \(\max(f(n), g(n)) \le f(n) + g(n)\) (because both are non-negative), we have: \[\max(f(n), g(n)) \le 1 \cdot (f(n) + g(n))\] Set \(c_2 = 1\), \(n_0 = 1\). So \(\max(f(n), g(n)) = O(f(n) + g(n))\).

\(\Omega\) bound: Since \(\max(f(n), g(n)) \ge f(n)\) and \(\max(f(n), g(n)) \ge g(n)\), adding: \[2 \cdot \max(f(n), g(n)) \ge f(n) + g(n)\] \[\max(f(n), g(n)) \ge \frac{1}{2}(f(n) + g(n))\] Set \(c_1 = 1/2\), \(n_0 = 1\). So \(\max(f(n), g(n)) = \Omega(f(n) + g(n))\).

By Theorem 3.1, \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\).

Answer: Proved with \(c_1 = 1/2\), \(c_2 = 1\), \(n_0 = 1\).

4.12. Prove \((n + a)^b = \Theta(n^b)\) (Lecture 1, Task 4)

Prove that \((n + a)^b = \Theta(n^b)\) for any constant \(a\) and any positive constant \(b\).

Click to see the solution

Key Concept: For large \(n\), the constant \(a\) becomes negligible compared to \(n\).

\(O\) bound: For \(n \ge |a|\), we have \(n + a \le n + |a| \le 2n\). Therefore: \[(n + a)^b \le (2n)^b = 2^b \cdot n^b\] Set \(c_2 = 2^b\) and \(n_0 = |a|\).

\(\Omega\) bound: For \(n \ge 2|a|\), we have \(n + a \ge n - |a| \ge n/2\). Therefore: \[(n + a)^b \ge (n/2)^b = \frac{1}{2^b} \cdot n^b\] Set \(c_1 = 1/2^b\) and \(n_0 = 2|a|\).

By Theorem 3.1, \((n + a)^b = \Theta(n^b)\).

Answer: Proved with \(c_1 = 1/2^b\), \(c_2 = 2^b\), \(n_0 = 2|a|\).

4.13. Prove Product Rule for \(O\)-notation (Lecture 1, Task 5)

Prove that if \(f(n) = O(n^2)\) and \(g(n) = O(\log n)\), then \(f(n) \cdot g(n) = O(n^2 \log n)\).

Click to see the solution

Key Concept: Multiply the upper bounds.

Since \(f(n) = O(n^2)\), there exist \(c_1, n_1 > 0\) with \(0 \le f(n) \le c_1 n^2\) for all \(n \ge n_1\).

Since \(g(n) = O(\log n)\), there exist \(c_2, n_2 > 0\) with \(0 \le g(n) \le c_2 \log n\) for all \(n \ge n_2\).

For \(n \ge n_0 = \max(n_1, n_2)\): \[0 \le f(n) \cdot g(n) \le c_1 n^2 \cdot c_2 \log n = (c_1 c_2) \cdot n^2 \log n\]

Set \(c = c_1 c_2\). This proves \(f(n) \cdot g(n) = O(n^2 \log n)\).

Answer: Proved with \(c = c_1 c_2\) and \(n_0 = \max(n_1, n_2)\).

4.14. Prove that \(k \ln k = \Theta(n)\) implies \(k = \Theta(n / \ln n)\) (Lecture 1, Task 6)

Prove that if \(k \ln k = \Theta(n)\), then \(k = \Theta\!\left(\frac{n}{\ln n}\right)\).

Click to see the solution

Key Concept: Use the relationship \(k \ln k = \Theta(n)\) to bound \(k\) and \(\ln k\) in terms of \(n\).

1. Establish bounds from \(k \ln k = \Theta(n)\).

Since \(k \ln k = \Theta(n)\), there exist constants \(c_1, c_2, n_0 > 0\) such that for \(n \ge n_0\): \[c_1 n \le k \ln k \le c_2 n\]

2. Upper bound on \(k\).

From \(c_1 n \le k \ln k\), since \(\ln k \le k\) for \(k \ge 1\), we get \(c_1 n \le k^2\), so \(k \ge \sqrt{c_1 n}\). This means \(k \to \infty\) as \(n \to \infty\).

From \(k \ln k \le c_2 n\), we get \(k \le c_2 n / \ln k\). Since \(k \ge \sqrt{c_1 n}\), we have \(\ln k \ge \frac{1}{2} \ln(c_1 n) = \Omega(\ln n)\).

3. Taking logarithms.

From \(c_1 n \le k \ln k \le c_2 n\):

Taking logarithm: \(\ln(c_1 n) \le \ln(k \ln k) = \ln k + \ln \ln k \le 2 \ln k\) for large \(k\).

Also \(\ln k \le \ln(k \ln k) \le \ln(c_2 n)\).

So \(\frac{1}{2}\ln(c_1 n) \le \ln k \le \ln(c_2 n)\), which gives \(\ln k = \Theta(\ln n)\).

4. Deriving the bound on \(k\).

From \(k \ln k = \Theta(n)\) and \(\ln k = \Theta(\ln n)\): \[k = \frac{\Theta(n)}{\ln k} = \frac{\Theta(n)}{\Theta(\ln n)} = \Theta\!\left(\frac{n}{\ln n}\right)\]

Answer: \(k = \Theta(n / \ln n)\).